package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/4 17:32
 */
public class J19 {

    /** https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/ */
    // 暴力计算
    public static boolean isMatch(String s, String p) {
        char[] a = s.toCharArray();
        char[] b = p.toCharArray();
        return process(a, b, a.length-1, b.length-1);
    }


    // String A = "aab"
    // String B = "c*a*b"
    private static boolean process(char[] A, char[] B, int N, int M) {
        if(N < 0) {
            // A 匹配完了, 如果B也匹配完了返回true, 否则看B的前边是否都是*
            if(M < 0) {
                return true;
            }else {
                while (M >= 0) {
                    if( B[M] != '*' ) {
                        return false;
                    }
                    M-=2;
                }
                return true;
            }
        }
        if(M < 0) {
            return false;
        }
        char c = B[M];
        if(c == '.') {
            // 遇到. A,B 直接往前跳
            return process(A, B, N-1, M-1);
        }else if(c == '*') {
            char pre = B[M-1];
            // A的这一个, 不匹配B的 ?*. B往前跳
            if( pre != '.' && A[N] != pre ) {
                return process(A, B, N, M-2);
            }else {
                // pre == . 或者匹配上了,
                // 匹配这个|A往前跳 | 匹配这个都往前跳 | 不匹配这个
                return process(A, B, N-1, M) || process(A, B, N-1, M-2) || process(A, B, N, M-2);
            }
        }else {
            // 匹配串的最后边是个 正常字符
            return A[N] == B[M] && process(A, B, N - 1, M - 1);
        }
    }


    // for test
    public static void main(String[] args) {
        String A = "aab";
        String B = "c*a*b";
        System.out.println(isMatch(A, B));
    }

}
